As a data compression algorithm, the LZ77 algorithm published by Abraham Lempel and Jacob Ziv in 1977 is known. The LZ77 algorithm is one example of a dictionary compression scheme, and is also referred to as a sliding dictionary scheme. In the LZ77 algorithm, data is encoded in order from the head. In the sliding dictionary scheme, a search is performed to determine whether a symbol string starting at a position of interest has previously appeared. When the symbol string has previously appeared, the symbol string is replaced with a pointer representing the appearance position and the length of the symbol string. The term “sliding dictionary scheme” originates from the fact that a range in which a symbol string is searched for is referred to as a “sliding window” and that the sliding window is used for a dictionary.
In the LZ77 algorithm, a data amount is reduced by replacing a repeatedly appearing data string with the length and the appearance position of a symbol string that has previously appeared. In decompression, original data can be decompressed by copying a symbol string having a matching length from a position where the symbol string has previously appeared and having a matching length. In addition, the LZ77 algorithm shows a method for encoding a length at which no repetition is detected and a symbol string that does not include any repetition when no repetition is detected.
Depending on an operating system (OS) of a Central Processing Unit (CPU), a Single Instruction Multiple Data (SIMD) instruction whereby plural pieces of data are handled when a single instruction is issued has been prepared, and data can be copied between memories in 16-byte or 32-byte units at high speed. When the SIMD instruction is used in copying processing in decompression, speeding-up of decompression can be realized.
[Non-Patent Document 1] Fiala, E. and Greene, D. (1989) “Data compression with finite windows” Communications of the ACM, 32(4) pp. 490-505